package LeetCode;

import java.util.HashMap;
import java.util.HashSet;

public class Code236_lowestCommonAncestor {
    // 1.递归遍历左子树与右子树
    // 终止条件：左子树包含P，右子树包含q；当前节点是p或q，另一个节点在其左子树或右子树中
    TreeNode p;
    TreeNode q;
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs(root);
        return res;
    }

    private boolean dfs(TreeNode root) {
        if (root == null){
            return false;
        }
        // 左右子树是否有p或q
        boolean inLeft = dfs(root.left);
        boolean inRight = dfs(root.right);
        if ((inLeft && inRight) || ((root.val == p.val) ||
                root.val == q.val) && (inLeft || inRight)){
            res = root;
        }
        return (inLeft || inRight) || (root.val == p.val ||
                root.val == q.val);
    }

    HashMap<TreeNode, TreeNode> parent = new HashMap<>();
    HashSet<TreeNode> visited = new HashSet<>();
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs2(root);
        // 找到p的所有祖先节点
        while (p != null){
            visited.add(p);
            p = parent.get(p);
        }
        while (q != null){
            if (visited.contains(q)){
                res = q;
                break;
            }
            q = parent.get(q);
        }
        return res;
    }

    private void dfs2(TreeNode root) {
        if (root.left != null){
            parent.put(root.left, root);
            dfs2(root.left);
        }
        if (root.right != null){
            parent.put(root.right, root);
            dfs2(root.right);
        }
    }
}
